package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/8 16:53
 * @Description:最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class Num236_LCA {
    // 最近公共祖先
    private TreeNode lca;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        findNode(root,p,q);
        return lca;
    }

    // 后序遍历的过程中查找p和q两个节点,只要找到一个就返回true
    // 若root为p和q的最近公共祖先，则p和q会出现在root的左子树、右子树或者root节点上的两个位置。
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        int left = findNode(root.left,p,q) ? 1 : 0;
        int right = findNode(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        // 相加为2表示p和q出现在三个位置的两个，因此root是p和q的最近公共祖先
        if (left + right + mid == 2) {
            lca = root;
            return true;
        }
        // 相加为0表示root不是p和q的公共祖先
        // 相加为1表示root可能是p也可能是q的祖先，但不是p和q的公共祖先
        return (left + right + mid > 0);
    }
}
